package com.mgq.algorithm.twotree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 完全二叉树
 * 要么每一层都是满的
 * 要么最后一层不满,但是左边有节点
 */
public class CST {
    /**
     * DP解决
     * 判断一棵树是否为完全二叉树?
     * 1.如果发现一棵树有右孩子,但是没有左孩子 直接返回false
     * 2.在条件1不违规的条件下,遇到了第一个左右2个孩子不全的情况下,那么接下来的所有节点都必须是叶子节点
     * 宽度优先遍历 (使用队列)
     *       4
     *      / \
     *     2   5
     *    / \  /
     *   1  3 7
     * 这就是一个完全二叉树
     * @param root
     * @return
     */
    public boolean isCST(TreeNode root) {
        if (root==null) return true;
        //用来标记第一个左右2个孩子不全
        boolean leaf = false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
                     //对应条件1 棵树有右孩子,但是没有左孩子 直接返回false
            if (    (node.right != null && node.left == null)
                    //遇到了第一个左右2个孩子不全的情况下,但是居然有孩子
                    ||(leaf&&(node.left!=null||node.right!=null)
            )) {
                return false;
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            //只要有一个为空,就满足 左右2个孩子不全
            if (node.left == null || node.right == null) {
                leaf = true;
            }
        }
        return true;
    }
}
